<TITLE>prob017: Ramsey numbers</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob017: Ramsey numbers</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT>
The Ramsey number R(k,l) is the smallest number such that every 
graph with this or more nodes either contains a clique of size k or an 
independent set of size l. 
Ramsey proved that such such a number exists for every (k,l) pair, 
but computing it has proven to be extremely difficult.

<P>
The problem can be posed as edge-colouring. The Ramsey number R(k,l) is
the smallest number such that if we two-colour the edges of 
complete graph of this size, there always
exists a monochromatic sub-graph of either k or l nodes.

<P>
A related problem (which is often called the Ramsey problem) is to 
colour the edges of a complete graph with n
nodes using at most k colours, in such a way that there is no monochromatic 
triangle in the graph, i.e. in any triangle at most two edges have the same 
colour.  With 3 colours, the problem has a solution if n < 17.    


<P>
There exist various interesting generalizations of Ramsey numbers
(e.g. to hypergraphs, to graphs which are complete except for a limited
number of edges, or to infinite size graphs). 

</TT>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


